/**********
This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)

This library is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
more details.

You should have received a copy of the GNU Lesser General Public License
along with this library; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
**********/
// Copyright (c) 1996-2018 Live Networks, Inc.  All rights reserved.
// Basic Hash Table implementation
// Implementation

#include "include/BasicHashTable.hh"
#include "../UsageEnvironment/include/strDup.hh"

#if defined(__WIN32__) || defined(_WIN32)
#else

#include <stddef.h>

#endif

#include <string.h>
#include <stdio.h>

// When there are this many entries per bucket, on average, rebuild
// the table to increase the number of buckets
#define REBUILD_MULTIPLIER 3

BasicHashTable::BasicHashTable(int keyType)
        : fBuckets(fStaticBuckets), fNumBuckets(SMALL_HASH_TABLE_SIZE),
          fNumEntries(0), fRebuildSize(SMALL_HASH_TABLE_SIZE * REBUILD_MULTIPLIER),
          fDownShift(28), fMask(0x3), fKeyType(keyType) {
    for (unsigned i = 0; i < SMALL_HASH_TABLE_SIZE; ++i) {
        fStaticBuckets[i] = NULL;
    }
}

BasicHashTable::~BasicHashTable() {
    // Free all the entries in the table:
    for (unsigned i = 0; i < fNumBuckets; ++i) {
        TableEntry *entry;
        while ((entry = fBuckets[i]) != NULL) {
            deleteEntry(i, entry);
        }
    }

    // Also free the bucket array, if it was dynamically allocated:
    if (fBuckets != fStaticBuckets) delete[] fBuckets;
}

void *BasicHashTable::Add(char const *key, void *value) {
    void *oldValue;
    unsigned index;
    TableEntry *entry = lookupKey(key, index);
    if (entry != NULL) {
        // There's already an item with this key
        oldValue = entry->value;
    } else {
        // There's no existing entry; create a new one:
        entry = insertNewEntry(index, key);
        oldValue = NULL;
    }
    entry->value = value;

    // If the table has become too large, rebuild it with more buckets:
    if (fNumEntries >= fRebuildSize) rebuild();

    return oldValue;
}

Boolean BasicHashTable::Remove(char const *key) {
    unsigned index;
    TableEntry *entry = lookupKey(key, index);
    if (entry == NULL) return False; // no such entry

    deleteEntry(index, entry);

    return True;
}

void *BasicHashTable::Lookup(char const *key) const {
    unsigned index;
    TableEntry *entry = lookupKey(key, index);
    if (entry == NULL) return NULL; // no such entry

    return entry->value;
}

unsigned BasicHashTable::numEntries() const {
    return fNumEntries;
}

BasicHashTable::Iterator::Iterator(BasicHashTable const &table)
        : fTable(table), fNextIndex(0), fNextEntry(NULL) {
}

void *BasicHashTable::Iterator::next(char const *&key) {
    while (fNextEntry == NULL) {
        if (fNextIndex >= fTable.fNumBuckets) return NULL;

        fNextEntry = fTable.fBuckets[fNextIndex++];
    }

    BasicHashTable::TableEntry *entry = fNextEntry;
    fNextEntry = entry->fNext;

    key = entry->key;
    return entry->value;
}

////////// Implementation of HashTable creation functions //////////

HashTable *HashTable::create(int keyType) {
    return new BasicHashTable(keyType);
}

HashTable::Iterator *HashTable::Iterator::create(HashTable const &hashTable) {
    // "hashTable" is assumed to be a BasicHashTable
    return new BasicHashTable::Iterator((BasicHashTable const &) hashTable);
}

////////// Implementation of internal member functions //////////

BasicHashTable::TableEntry *BasicHashTable
::lookupKey(char const *key, unsigned &index) const {
    TableEntry *entry;
    index = hashIndexFromKey(key);

    for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) {
        if (keyMatches(key, entry->key)) break;
    }

    return entry;
}

Boolean BasicHashTable
::keyMatches(char const *key1, char const *key2) const {
    // The way we check the keys for a match depends upon their type:
    if (fKeyType == STRING_HASH_KEYS) {
        return (strcmp(key1, key2) == 0);
    } else if (fKeyType == ONE_WORD_HASH_KEYS) {
        return (key1 == key2);
    } else {
        unsigned *k1 = (unsigned *) key1;
        unsigned *k2 = (unsigned *) key2;

        for (int i = 0; i < fKeyType; ++i) {
            if (k1[i] != k2[i]) return False; // keys differ
        }
        return True;
    }
}

BasicHashTable::TableEntry *BasicHashTable
::insertNewEntry(unsigned index, char const *key) {
    TableEntry *entry = new TableEntry();
    entry->fNext = fBuckets[index];
    fBuckets[index] = entry;

    ++fNumEntries;
    assignKey(entry, key);

    return entry;
}

void BasicHashTable::assignKey(TableEntry *entry, char const *key) {
    // The way we assign the key depends upon its type:
    if (fKeyType == STRING_HASH_KEYS) {
        entry->key = strDup(key);
    } else if (fKeyType == ONE_WORD_HASH_KEYS) {
        entry->key = key;
    } else if (fKeyType > 0) {
        unsigned *keyFrom = (unsigned *) key;
        unsigned *keyTo = new unsigned[fKeyType];
        for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i];

        entry->key = (char const *) keyTo;
    }
}

void BasicHashTable::deleteEntry(unsigned index, TableEntry *entry) {
    TableEntry **ep = &fBuckets[index];

    Boolean foundIt = False;
    while (*ep != NULL) {
        if (*ep == entry) {
            foundIt = True;
            *ep = entry->fNext;
            break;
        }
        ep = &((*ep)->fNext);
    }

    if (!foundIt) { // shouldn't happen
#ifdef DEBUG
        fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]);
        if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext);
        fprintf(stderr, ")\n");
#endif
    }

    --fNumEntries;
    deleteKey(entry);
    delete entry;
}

void BasicHashTable::deleteKey(TableEntry *entry) {
    // The way we delete the key depends upon its type:
    if (fKeyType == ONE_WORD_HASH_KEYS) {
        entry->key = NULL;
    } else {
        delete[] (char *) entry->key;
        entry->key = NULL;
    }
}

void BasicHashTable::rebuild() {
    // Remember the existing table size:
    unsigned oldSize = fNumBuckets;
    TableEntry **oldBuckets = fBuckets;

    // Create the new sized table:
    fNumBuckets *= 4;
    fBuckets = new TableEntry *[fNumBuckets];
    for (unsigned i = 0; i < fNumBuckets; ++i) {
        fBuckets[i] = NULL;
    }
    fRebuildSize *= 4;
    fDownShift -= 2;
    fMask = (fMask << 2) | 0x3;

    // Rehash the existing entries into the new table:
    for (TableEntry **oldChainPtr = oldBuckets; oldSize > 0;
         --oldSize, ++oldChainPtr) {
        for (TableEntry *hPtr = *oldChainPtr; hPtr != NULL;
             hPtr = *oldChainPtr) {
            *oldChainPtr = hPtr->fNext;

            unsigned index = hashIndexFromKey(hPtr->key);

            hPtr->fNext = fBuckets[index];
            fBuckets[index] = hPtr;
        }
    }

    // Free the old bucket array, if it was dynamically allocated:
    if (oldBuckets != fStaticBuckets) delete[] oldBuckets;
}

unsigned BasicHashTable::hashIndexFromKey(char const *key) const {
    unsigned result = 0;

    if (fKeyType == STRING_HASH_KEYS) {
        while (1) {
            char c = *key++;
            if (c == 0) break;
            result += (result << 3) + (unsigned) c;
        }
        result &= fMask;
    } else if (fKeyType == ONE_WORD_HASH_KEYS) {
        result = randomIndex((uintptr_t) key);
    } else {
        unsigned *k = (unsigned *) key;
        uintptr_t sum = 0;
        for (int i = 0; i < fKeyType; ++i) {
            sum += k[i];
        }
        result = randomIndex(sum);
    }

    return result;
}
